package com.jeff.learn.linkedlist;

import java.util.Iterator;
import java.util.Objects;
import java.util.function.Consumer;

/**
 * 单向链表的实现
 * 本实现中, 哨兵节点的下一个节点指向链表的第一个节点 sentinel.getNext()=>head
 *
 * @author yaojianfeng
 */
public class SinglySentinelLinkedList implements Iterable<Node> {

    /**
     * 哨兵节点
     */
    private Node sentinel = new Node(-1);


    public SinglySentinelLinkedList() {

    }


    public void addHead(int data) {
        // 在链表头部添加一个新节点
        Node newHead = new Node(data);
        // 设置新节点的下一个节点为当前哨兵节点的下一个节点
        newHead.setNext(sentinel.getNext());
        // 将哨兵节点的下一个节点指向新节点
        sentinel.setNext(newHead);
    }

    /**
     * 在链表尾部添加一个新节点
     *
     * @param data
     */
    public void addTail(int data) {
        Node newTail = new Node(data);
        Node last = findLast();
        // 设置当前节点的下一个节点为新节点
        last.setNext(newTail);
    }

    /**
     * 查找链表的最后一个节点
     *
     * @return
     */
    private Node findLast() {
        Node current = sentinel.getNext();
        // 如果链表为空，则直接将新节点设置为哨兵节点的下一个节点
        if (current == null) {
            // 链表为空，返回哨兵节点
            return sentinel;
        }
        // 遍历链表，找到最后一个节点
        while (current.getNext() != null) {
            // 直到找到最后一个节点
            current = current.getNext();
        }
        return current;
    }

    /**
     * 根据索引查找节点
     *
     * @param index
     */
    public Node findNode(int index) {
        if (index < 0) {
            return null;
        }
        Node current = sentinel.getNext();
        int i = 0;
        while (current != null) {
            if (i == index) {
                break;
            }
            current = current.getNext();
            i++;
        }
        return current;
    }

    /**
     * 根据索引删除节点
     *
     * @param index
     * @return
     */
    public Node removeNode(int index) {
        //参数校验
        if (index < 0) {
            throw new IllegalArgumentException("index must be greater than or equal to 0");
        }
        // 找到要删除的节点
        Node current = findNode(index);
        // 找到要删除节点的前一个节点
        Node prev = findNode(index - 1);

        if (current != null) {
            if (prev == null) {
                //当前节点的前一个节点为空,说明要删除的是头节点    删除头节点
                return removeHead();
            } else {
                // 删除中间节点
                prev.setNext(current.getNext());
            }
            return current;
        }
        return current;
    }

    /**
     * 删除头节点
     *
     * @return 删除的头节点
     */
    private Node removeHead() {
        Node head = sentinel.getNext();
        Node next = head.getNext();
        sentinel.setNext(next);
        return head;
    }

    /**
     * 遍历链表
     *
     * @param action
     */
    public void foreach(Consumer<Node> action) {
        Node current = sentinel.getNext();
        while (current != null) {
            action.accept(current);
            current = current.getNext();
        }
    }

    /**
     * 向指定插入节点
     *
     * @param index   索引位置
     * @param newNode 新节点
     * @return 是否插入成功
     */
    public boolean insertNode(int index, Node newNode) {
        //newNode 不能为空
        Objects.requireNonNull(newNode);
        if (index < 0) {
            return false;
        }
        if (index == 0) {
            addHead(newNode.getValue());
            return true;
        }

        // 插入到中间节点
        Node pre = findNode(index - 1);
        if (pre != null) {
            newNode.setNext(pre.getNext());
            pre.setNext(newNode);
        } else {
            return false;
        }
        return true;
    }

    @Override
    public Iterator<Node> iterator() {
        return new Iterator<Node>() {
            //声明当前节点 指向哨兵节点
            private Node current = sentinel;

            @Override
            public boolean hasNext() {
                return current.getNext() != null;
            }

            @Override
            public Node next() {
                current = current.getNext();
                return current;
            }

            @Override
            public void forEachRemaining(Consumer<? super Node> action) {
                Objects.requireNonNull(action);
                while (hasNext())
                    action.accept(next());
            }
        };

    }


}
